<h1>bias</h1>

<ul>
<li> <a href="#1">When not to use this code</a>
<li> <a href="#2">Code</a>
<ul>
<li> <a href="#3">Uses</a>
<li> <a href="#4">Top-level Drivers</a>
<ul>
<li> <a href="#5">sample</a>
<li> <a href="#6">sampleCounts</a>
</ul>
<li> <a href="#7">Workers</a>
<ul>
<li> <a href="#8">a2cdf</a>
<li> <a href="#9">a2best</a>
<li> <a href="#10">sorted2cdf</a>
<li> <a href="#11">Pick</a>
</ul>
</ul>
<li> <a href="#12">Author</a>
</ul>
<p>
Given a frequency counts of a population, generate numbers biased by those frequencies.
</p>
<p>
For demo of this code, see <a href="?biasDemo">biasDemo</a>.
</p>
<a name="1"></a><h2>When not to use this code</h2>
<p>
If you sampling from small populations (say, two dozen or less), 
just sample the population at the rate you want, throw those samples into an
array, then select at item of that array at random.
</p>
<p>
E.g. suppose you just want to pick at random from a set of quotes:
</p>
<pre>
  Quotes = "Small  things with great love. &lt;br>-- Mother Teresa\n\
            It's hard work to it look effortless.&lt;br>-- Katarina Witt\n\
            God bless us every one!.&lt;br>-- Tiny Tim"
   srand(systime() + PROCINFO["pid"])
   n=split(Quotes,tmp,"\n")
   print  tmp[int(rand()*n) + 1]
</pre>
<p>
Use the following code if you are sampling from larger populations with
complex distributions.
</p>
<a name="2"></a><h2>Code</h2>

<a name="3"></a><h3>Uses</h3>
<p>
<a href="?o">o</a> <a href="?math">math</a> <a href="?s2a">s2a</a> 
</p>
<a name="4"></a><h3>Top-level Drivers</h3>

<a name="5"></a><h4>sample</h4>
<p>
Sample from population of things.
</p>
<pre>
 function sample(population,cdf,memo,   count,one) { 
     for(one in population) 
         count[population[one]]++
     return sampleCounts(count,cdf,memo)
 }
</pre>
<a name="6"></a><h4>sampleCounts</h4>
<p>
Sample of a list of counted things.
</p>
<pre>
 function sampleCounts(counts,cdf,memo,   all, one,x,f,i) {
     for(one in counts)
         all += counts[one]
     for(one in counts) {
         x = (1000*counts[one]/all)+ rand()/100
         f[++i]= x
         memo[x] = one
     }
     a2cdf(f,cdf)
     return i
 }
</pre>
<a name="7"></a><h3>Workers</h3>

<a name="8"></a><h4>a2cdf</h4>
<p>
Prepare an array of numbers, prior to picking. 
Internally, this code 
converts an array of numbers into a cdf. From
<a href="http://www.aiaccess.net/English/Glossaries/GlosMod/e<em>gm</em>distribution_function.htm">aiaccess.net</a>: 
</p>
<ul>
<li> A <em>cdf</em> (or "cumulative distribtion function") is the proportion of the population whose value is less than x.  The <em>cdf</em> of  a random variable is clearly a monotonously increasing (or more precisely, non decreasing) function from 0 to 1.
</ul>
<p>
In Awk, we can represent this as an array of  "<em>n</em>" symbols stored at
locations 1,2,3..n and a set of increasing probabilities  locations
-1,-2,-3,...-n (where -i is the probability of symbol i). 
</p>
<pre>
    This kind of array is generated by `a2cdf`:


 function a2cdf(a,cdf, sorted,n) {
     n= a2best(a,sorted)
     return sorted2cdf(n,sorted,cdf)
 }
</pre>
<a name="9"></a><h4>a2best</h4>
<p>
If "<em>a</em>" is an array of numbers,  then sort them in ascending order.
If <em>max</em> is supplied, return no more than the first <em>max</em> number of values. 
</p>
<pre>
 function a2best(a,best,  max,    sorted,n,i,j) {
                #must     opt     local
     n = asort(a,sorted);
     if (max && n >= max) {
         for(i = n - max + 1; i&lt;=n; i++)
             best[++j] = sorted[i];
         n= max;
     } 
     else 
         for(i in sorted)
             best[i]=sorted[i];
     return n;
 }
</pre>
<a name="10"></a><h4>sorted2cdf</h4>
<pre>
 function sorted2cdf(n,sorted,cdf,    i,j,sum) {
     if (! (1 in sorted)) 
         return (cdf[0]=split("",cdf,""))
     sum = cdf[1] = sorted[1];
     for(i=2;i&lt;=n;i++) { 
         sum += sorted[i];
         cdf[i] = cdf[i-1] + sorted[i];
     }
     for(i in cdf)  
         cdf[i] = cdf[i] / sum;
     for(i=1;i&lt;=n;i++)
         cdf[-1*i] = sorted[i]
     cdf[0]=n
     return n
 }
</pre>
<a name="11"></a><h4>Pick</h4>
<p>
Return one symbol from a <em>cdf</em>, biased by the <em>cdf</em> probabilities. 
If <em>skew</em> is provided, bias the selection towards one end of the
distribtion. The larger the <em>skew</em> (above one), the more we favor
things with higher probabilities. It <em>skew</em> is one, the just
draw from the supplied distribution.
</p>
<pre>
 function pick(cdf,  skew,   i) {
               #must   opt     local
     i = pick1(cdf,cdf[0],skew)
     return cdf[-1*i]
 }
 function pick1(cdf,n,  skew,u,i,here) {
     skew = skew ? skew : 1
     u = rand()^skew 
     for(i=n-1;i>=1;i--) 
         if (u > cdf[i] ) 
             return i+1;
     return 1;
 }
</pre>
<a name="12"></a><h2>Author</h2>
<p>
Tim Menzies
